package com.future;

/**
 * Description: 62. 不同路径
 *
 * @author weiruibai.vendor
 * Date: 2022/7/6 14:10
 */
public class Solution_62 {


    public static void main(String[] args) {
        int m = 3;
        int n = 7;
        /*m = 3;
        n = 3;*/
        m = 51;
        n = 9;
        System.out.println(uniquePaths_dp(m, n));
        System.out.println("===");
        System.out.println(uniquePaths(m, n));
    }

    /**
     * 暴力超时
     *
     * @param m
     * @param n
     * @return
     */
    public static int uniquePaths_dp(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = -1;
            }
        }
        return process_dp(m, 0, n, 0, dp);
    }

    private static int process_dp(int m, int i, int n, int j, int[][] dp) {
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        int val = 0;
        if (i == m || j == n) {
            val = 0;
        } else if (i == m - 1 && j == n - 1) {
            val = 1;
        } else if (i == m - 1) {
            // 来到最右，只能向下
            val = process_dp(m, i, n, j + 1, dp);
        } else if (j == n - 1) {
            // 来到最底，只能向右
            val = process_dp(m, i + 1, n, j, dp);
        } else {
            // 普遍场景
            // 1、向右
            int count1 = process_dp(m, i + 1, n, j, dp);
            // 2、向下
            int count2 = process_dp(m, i, n, j + 1, dp);
            val = count1 + count2;
        }
        dp[i][j] = val;
        return val;
    }

    /**
     * 暴力超时
     *
     * @param m
     * @param n
     * @return
     */
    public static int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        return process(m, 0, n, 0);
    }

    private static int process(int m, int i, int n, int j) {
        if (i >= m || j >= n) {
            return 0;
        }
        if (i == m - 1 && j == n - 1) {
            return 1;
        }
        // 来到最右，只能向下
        if (i == m - 1) {
            return process(m, i, n, j + 1);
        } else if (j == n - 1) {
            // 来到最底，只能向右
            return process(m, i + 1, n, j);
        } else {
            // 普遍场景
            // 1、向右
            int count1 = process(m, i + 1, n, j);
            // 2、向下
            int count2 = process(m, i, n, j + 1);
            return count1 + count2;
        }
    }

}
